#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* partition(ListNode* head, int x) {
//        if (!head) return nullptr;
//        ListNode* cur = head, * newhead1 = new ListNode(-1), * newhead2 = new ListNode(-1);
//        ListNode* p1 = newhead1, * p2 = newhead2;
//        while (cur)
//        {
//            if (cur->val < x)
//            {
//                newhead1->next = cur;
//                newhead1 = newhead1->next;
//            }
//            else
//            {
//                newhead2->next = cur;
//                newhead2 = newhead2->next;
//            }
//            ListNode* tmp = cur->next;
//            cur->next = nullptr;
//            cur = tmp;
//        }
//        newhead1->next = p2->next;
//        return p1->next;
//    }
//};
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        ListNode* head = new ListNode(1);
//        ListNode* cur1 = list1, * cur2 = list2, * ans = head;
//        while (cur1 && cur2)
//        {
//            if (cur1->val > cur2->val)
//            {
//                head->next = cur2;
//                ListNode* tmp = cur2->next;
//                cur2->next = nullptr;
//                cur2 = tmp;
//            }
//            else
//            {
//                head->next = cur1;
//                ListNode* tmp = cur1->next;
//                cur1->next = nullptr;
//                cur1 = tmp;
//            }
//            head = head->next;
//        }
//        if (cur1) head->next = cur1;
//        else head->next = cur2;
//        return ans->next;
//    }
//};
int main()
{
	return 0;
}